package net.tp.struct.bst;

/**
 *
 * <p>Top-down Splay Tree.</p>
 *
 * <p>Normal Splay tree have to do traversal down and up. The top-down splay tree only traverse down and splay the nodes
 * a long the way.</p>
 *
 * <p>To do this, we need to maintain $O(1)$ extra storage, but reduce the space overall by not maintaining the parent pointer
 * in each node. The extra space is needed to maintain left tree L and its max node, right tree R and its min node.</p>
 *
 * <p>At any point in the middle of the splay operation, we have the middle tree rooted at current node X,
 * the left tree L that contains elements smaller than tree X elements, the right tree T that contains elements
 * larger than tree X elements. The L and R trees are null initially.</p>
 *
 * <h3>Splay operation</h3>
 *
 * <pre>
 *     L              A           R       zig-zig ⇒    L        C          R
 *     △         ┌────┴────┐      △                    △      ┌─┴─┐        △
 *               B         △                                  △   △      ┌─┴ ← min node
 *            ┌──┴──┐      4                                  1   2      B ← new min node
 *            C     △                                                    ┴─┐
 *          ┌─┴─┐   3                                                      A
 *          △   △                                                        ┌─┴─┐
 *          1   2                                                        △   △
 *                                                                       3   4
 *
 *
 *     L              A           R       zig-zag ⇒   L       B            R
 *     △         ┌────┴────┐      △                   △    ┌──┴──┐         △
 *               B         △                               △     C       ┌─┴ ← min node
 *            ┌──┴──┐      4                               1   ┌─┴─┐     A ← new min node
 *            △     C                                          △   △     ┴─┐
 *            1   ┌─┴─┐                                        2   3       △
 *                △   △                                                    4
 *                2   3
 *
 *
 *     L              A           R       zig     ⇒   L       B            R
 *     △         ┌────┴────┐      △                   △    ┌──┴──┐         △
 *               B         △                               △     △       ┌─┴ ← min node
 *            ┌──┴──┐      3                               1     2       A ← new min node
 *            △     △                                                    ┴─┐
 *            1     2                                                      △
 *           at least 1 or 2                                               3
 *           is null
 *
 *
 *
 *     L              A           R    reassemble ⇒                A
 *     △         ┌────┴────┐      △                            ┌───┴───┐
 *     1         △         △      4                            △       △
 *               2         3                                   1       4
 *                                                  max node → ┴─┐   ┌─┴ ← min node
 *                                                               △   △
 *                                                               2   3
 * </pre>
 *
 * <h3>Join operation</h3>
 *
 * <p>Join 2 tree A, B (all elements of A &lt; all elements of B):</p>
 *
 * <pre>
 * △   △      Splay    ⇒         X     △       Make A ⇒          X
 * A   B      max node        ┌──┴     B       child          ┌──┴──┐
 *            of A            △                of X           △     △
 *                            A                               A     B
 * </pre>
 *
 * <h3>Split operation</h3>
 *
 * <p>Splay the node containing x or successor/predecessor of x (if x does not exist in the tree),
 * then cut the left or right link of node x:</p>
 *
 * <pre>
 * Splay ⇒       X      Split X's  ⇒           X      △
 * X to       ┌──┴──┐   right link          ┌──┴      B
 * root       △     △                       △
 *            A     B                       A
 * </pre>
 *
 * <h3>Insert operation</h3>
 *
 * <p>To insert x into the tree (assuming x does not exist), split the tree at x, then create new node x with left
 * and right child pointing to the trees that are cut:</p>
 *
 * <pre>
 *    △  ⇒   △    △   ⇒        X
 *           A    B         ┌──┴──┐
 *                          △     △
 *                          A     B
 * </pre>
 *
 * <h3>Delete operation</h3>
 *
 * <p>Split the trees at node x, then join the two trees:</p>
 *
 * <pre>
 *    △  ⇒       X      ⇒    △    △   ⇒     Y     △     ⇒       X
 *            ┌──┴──┐        A    B      ┌──┴     B          ┌──┴──┐
 *            △     △                    △                   △     △
 *            A     B                    A                   A     B
 * </pre>
 *
 *
 *
 *
 * @author Trung Phan
 *
 */
public class TopDownSplayTree<K, V> {




    /**
     * This is compact node without parent pointer.
     * @param <K> Key type
     * @param <V> Value type
     */
    public static class Node<K, V> {
        public Node<K, V> left;
        public Node<K, V> right;
        public K key;
        public V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}
